Nowadays there are many social media sites with a very large number of users. Users of social media sitesand relationships between them can be modelled as a graph. Such graphs can be analysed using methodsfrom social network analysis (SNA). Many measures used in SNA rely on computation of shortest pathsbetween nodes of a graph. There are many shortest path algorithms, but the majority of them suits only forsmall graphs, or work only with road network graphs that are fundamentally different from social graphs.This paper describes an efficient shortest path searching algorithm suitable for large social graphs. Thedescribed algorithm extends the Atlas algorithm. The proposed algorithm solves the shortest path problemin social graphs modelling sites with over 100 million users with acceptable response time (50 ms perquery), memory usage (less than 15 GB of the primary memory) and applicable accuracy (higher than 90%of the queries return exact result).
展开▼
